1. Field of the Invention
The invention relates to systems and methods for processing Access Control Lists (ACLs) used in network communications, such as in Ethernet switches, using regular expression matching logic.
2. Description of the Related Art
ACLs are commonly used in Ethernet switching devices to control the flow of packet traffic through the switching devices in order to protect networks from unauthorized access, for example. An ACL typically determines whether or not a packet should be allowed to pass through the switch and on to one or more computing device that are in communication with the switch. An ACL typically includes a list of rules, where each rules comprises a qualification pattern indicating one or more attributes of packets, and an action corresponding to each qualification pattern that is performed if the qualification pattern is matched by a packet. Portions of the packet, such as information in the packet headers, is compared to the qualification patterns in order to determine if the packet data, referred to herein as the packet's qualification content, matches the qualification patterns of the ACL. If a qualification pattern of the ACL matches the packet's qualification content, an action associated with the qualification pattern is executed. The qualification patterns and qualification content may comprise various components of packets, such as IP and TCP headers, including a combination of Ethernet frame (MAC) fields, Internet Protocol (IP) addresses and Transmission Control Protocol (TCP) port and protocol information. One or more components of a packet's 7-tuple, which comprises a source MAC address, destination MAC address, source IP address, destination IP address, source TCP port, destination TCP port and protocol, may be considered by qualification patterns in an ACL. In order to control flow of packets, each qualification pattern of the ACL is associated with one or more actions that are executed in response to fulfillment of the rule. An action may be to allow a packet to flow through the switch or to deny the packet from flowing through the switch.
Switching implementations typically use a ternary match methodology to establish an “exact match” of a packet's qualification content on the ACL qualification patterns in order to execute the associated actions, e.g., permit or deny passage of the packet. ACL qualification patterns may be specified as ternary exact matches on the packets ACL qualification content, such as the 7-tuple. U.S. Pat. No. 6,651,096 titled “Method and apparatus for organizing, storing and evaluating access control lists,” which is hereby incorporated by reference in its entirety, describes ACL's wherein each field represents a specific address, range of addresses or “don't care” value. Some examples of ACLs are:
Qualification patternAction1source_mac = 00:00:12:f8:03:23Permit2source_IP = 10.10.3.0/24 destination_IP = 10.10.0.0/16Permit3destination_IP = 10.10.2.0/24Deny4source_IP = 10.10.1.0/24PermitImplementation of such an ACL is executed in order until the first definitive qualification pattern is matched by a packet's qualification content. For example, with the above ACL a packet with the 7-tuple:                Source_mac=00:00:12:af:b9:83        Destination_mac=00:00:12:af:b3:12        Source_IP=10.10.3.12        Destination_IP=10.10.2.2        Source_Port=2383        Destination_Port=80        Protocol=http            would not be affected by rule 1 (the source_mac is different than the source_mac in qualification pattern 1), but would be permitted by rule 2 (the source_IP and the destination_IP of the packet's qualification content match the source_IP and destination_IP of qualification pattern 2). However the 7-tuple:            Source_mac=00:00:12:af:b9:83        Dest_mac=00:00:12:af:b3:12        Source_ID=10.10.1.12        Dest_IP=10.10.2.2        Source_Port=2383        Dest_Port=80        Protocol=http            would match qualification pattern 3, and thus be denied passage through the Ethernet switch. More particularly, the qualification content, e.g., the packet's 7-tuple, does not match qualification pattern 1 because the source_MAC of the packet is different than that specified in qualification pattern 1; the packet does not match qualification pattern 2 because the source_IP of the packet does not match the source_IP range of qualification pattern 2. However, with the subnet mask “/24” of qualification pattern 3, e.g., indicating that only the first 24 bits of the 32 bit IP address are to be considered by the qualification pattern, the destination_IP of 10.10.2.2 satisfies qualification pattern 3.
ACL rulesets typically evaluate every packet on ingress and/or egress from an Ethernet switch. ACL rule processing has typically been implemented in systems using software processing or Ternary Content Addressable Memories (TCAMs). Since ACLs require a true exact match (with ternary exclusions) and since the majority of packets will match at least one entry, traditional algorithmic acceleration methods (such as hashing) for high-speed match sorting are not effective. Additionally, the silicon area and power required to process an ACL using TCAMs grows linearly (or greater) as the number of rules and depth of search into each packet grows. This limits the number of ACLs that can be configured in a system, restricting the security that can be applied.